Number of ways to paint NX3 grid [Matrix Exponentiation]

Time: O(LogN); Space: O(1); hard

You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colours: Red, Yellow or Green while making sure that no two adjacent cells have the same colour (i.e no two cells that share vertical or horizontal sides have the same colour).

You are given n the number of rows of the grid.

Return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: n = 1

Output: 12

Explanation:

There are 12 possible way to paint the grid as shown:

Example 1:

Input: n = 2

Output: 54

Example 3:

Input: n = 3

Output: 246

Example 4:

Input: n = 7

Output: 106494

Example 5:

Input: n = 5000

Output: 30228214

Constraints:

  • n = len(grid)

  • len(grid[i]) = 3

  • 1 <= n <= 5000

Hints:

  1. We will use Dynamic programming approach. we will try all possible configuration.

  2. Let dp[idx][prev1col][prev2col][prev3col] be the number of ways to color the rows of the grid from idx to n-1 keeping in mind that the previous row (idx - 1) has colors prev1col, prev2col and prev3col. Build the dp array to get the answer.

1. Dynamic programming (Matrix Exponentiation) [O(LogN), O(1)]

[5]:

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(1)
    """
    def numOfWays(self, n):
        """
        :type n: int
        :rtype: int
        """
        def matrix_mult(m1, m2):
            return [[sum(a * b for a, b in zip(m1_row, m2_col)) %MOD for m2_col in zip(*m2)] for m1_row in m1]

        def matrix_expo(m, pow):
            assert pow >= 0 and int(pow) == pow, "Only non-negative, integer powers allowed"
            result = [[int(i==j) for j in range(len(m))] \
                                 for i in range(len(m))]
            while pow:
                if pow % 2:
                    result = matrix_mult(result, m)
                m = matrix_mult(m, m)
                pow //= 2
            return result

        MOD = 10**9 + 7
        T = [[3, 2],
             [2, 2]]

        return sum(matrix_mult([[6, 6]], matrix_expo(T, n-1))[0]) % MOD     # [a1, a0] * T^(n-1)

[6]:

s = Solution1()

n = 1
assert s.numOfWays(n) == 12
n = 2
assert s.numOfWays(n) == 54
n = 3
assert s.numOfWays(n) == 246
n = 7
assert s.numOfWays(n) == 106494
n = 5000
assert s.numOfWays(n) == 30228214

2.

[7]:

class Solution2(object):
    def numOfWays(self, n):
        """
        :type n: int
        :rtype: int
        """
        MOD = 10**9 + 7
        aba, abc = 6, 6

        for _ in range(n-1):
            aba, abc = (3*aba%MOD + 2*abc%MOD)%MOD, \
                       (2*abc%MOD + 2*aba%MOD)%MOD

        return (aba+abc)%MOD

[8]:

s = Solution2()

n = 1
assert s.numOfWays(n) == 12
n = 2
assert s.numOfWays(n) == 54
n = 3
assert s.numOfWays(n) == 246
n = 7
assert s.numOfWays(n) == 106494
n = 5000
assert s.numOfWays(n) == 30228214